package com.colter.project.data.structure.heap;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
/**
 * 1 构建一个最大堆（添加一个元素）
 *  每当向最大堆添加一个元素时，把该元素放到堆的末尾。
 *  比较该元素结点与父节点，如果大于父节点，则调换其位置，（该节点此时位于父节点的位置）
 *  继续比较与新的父节点的大小，直到找到比其大的父节点，或者直到顶点
 * 2 删除顶节点
 *   直接删除顶点，然后把最后一个叶子结点替换到顶点位置。（此时顶点的值为最后的叶子结点的值），删除最后的叶子节点
 *   比较顶点与最大的子节点的大小，如果小于最大的子节点，则交换位置，
 *   继续比较与新的最大子节点的值，直到比最大的子节点值大，或者没有子节点（即是叶子节点）。
 * @author user
 *
 * @param <T>
 */
public class OldMaxHeap<T extends Comparable<T>> {
	private List<T> list;
	private int cursor;

	public OldMaxHeap() {
		list = new ArrayList<>();
		cursor = -1;
	}

	void shiftUp(int index) {
		T intent = list.get(index);
		while (index > 0) {
			int pindex = (index - 1) / 2;
			T parent = list.get(pindex);
			if (intent.compareTo(parent) > 0) {
				list.set(index, parent);
				list.set(pindex, intent);
				index = pindex;
			} else {
				break;
			}
		}
	}

	void shiftDown(int index) {
		while (index < list.size()) {
			T intent = list.get(index);
			int lindex = index * 2 + 1;
			int rindex = index * 2 + 2;
			// 2个子节点
			if (rindex < list.size()) {
				int mindex = lindex;
				if (list.get(lindex).compareTo(list.get(rindex)) > 0) {
					mindex = lindex;
				} else {
					mindex = rindex;
				}

				if (intent.compareTo(list.get(mindex)) < 0) {
					list.set(index, list.get(mindex));
					list.set(mindex, intent);
					index = mindex;
				} else {
					break;
				}
			} else if (lindex >= list.size()) {
				index = list.size();
				break;
				// 只有1个子节点
			} else if (lindex < list.size() && rindex >= list.size()) {
				if (intent.compareTo(list.get(lindex)) < 0) {
					list.set(index, list.get(lindex));
					list.set(lindex, intent);
					index = lindex;
				} else {
					break;
				}
			}
		}

	}

	public void removeTop() {
		if (isEmpty()) {
			throw new RuntimeException("No such element.");
		}
		T lastItem = list.get(list.size() - 1);
		list.set(0, lastItem);
		list.remove(list.size() - 1);
		shiftDown(0);
	}

	public void add(T t) {
		list.add(t);
		shiftUp(list.size() - 1);
	}

	public boolean isEmpty() {
		return list.isEmpty();
	}

	public T getTop() {
		return list.get(0);
	}

	@Override
	public String toString() {
		return "OldMaxHeap [list=" + list + ", cursor=" + cursor + "]";
	}

	public static void main(String[] args) {
		OldMaxHeap<Integer> heap = new OldMaxHeap<>();
		Random r = new Random();
		for (int i = 0; i < 15; i++) {
			heap.add(r.nextInt(100));
		}

		// OldMaxHeap<Integer> heap = new OldMaxHeap<>();
		// heap.add(1);
		// heap.add(3);
		// heap.add(9);
		// heap.add(2);
		// heap.add(12);
		// heap.add(7);
		// heap.add(6);
		// heap.add(10);
		// heap.add(8);

		System.out.println(heap);
		while (!heap.isEmpty()) {
			System.out.println(heap.getTop());
			heap.removeTop();
		}

	}
}
